package hot;

/**
 * @author lakersUp
 * @Classname   跳跃游戏
 * @Description     动态规划  更适合贪心
 * @Date 2022/3/10 9:00
 * @Version 1.0
 */
public class Hot55canJump {
    //动态规划
//    public boolean canJump(int[] nums) {
//        int n=nums.length;
//        boolean[] dp=new boolean[n];
//        dp[0]=true;
//        for(int i=1;i<n;i++){
//            for(int j=0;j<i;j++){
//                if(dp[j]==true && (j+nums[j])>=i){
//                    dp[i]=true;
//                    break;
//                }
//            }
//        }
//        return dp[n-1];
//    }

    //贪心
    public boolean canJump(int[] nums) {
        int rightmost=0;
        int n=nums.length;
        for(int i=0;i<n;i++){
            if(i<=rightmost){
                rightmost=Math.max(rightmost,i+nums[i]);
                if(rightmost>=n-1){
                    return true;
                }
            }
        }
        return false;
    }
}
